package com.xinxin.leetcode.problem572;

import com.xinxin.leetcode.common.TreeNode;
import com.xinxin.leetcode.common.TreeUtil;

/**
 * @author ShiXinXin
 * @date 2020-02-07 12:35
 */
class Solution {
    public boolean isTree(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null || s.val != t.val) {
            return false;
        }
        return isTree(s.left, t.left) && isTree(s.right, t.right);
    }

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if ((s == null)) {
            return false;
        }
        if (t == null) {
            return true;
        }
        if (isTree(s, t)) {
            return true;
        } else {
            return isSubtree(s.left, t) || isSubtree(s.right, t);
        }
    }

    public static void main(String[] args) {
        TreeNode r = TreeUtil.createTree(new int[]{3, 4, 1, 0, 0, 2, 0, 0, 5, 0, 0});
        TreeNode s = TreeUtil.createTree(new int[]{4, 1, 0, 0, 2, 0, 0});
        System.out.println(new Solution().isSubtree(r, s));
    }
}
